package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/6/13 22:00
 */
public class C77 {


    List<List<Integer>> ans;
    ArrayList<Integer> list;

    // 长度为k的组合
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>(n);
        list = new ArrayList<>(k);
        process(1, n, k);
        return ans;
    }

    public void process(int i, int N, int rest) {
        if(rest < 0) return;
        if (i > N) {
            if (rest == 0)
                ans.add(new ArrayList<>(list));
        } else {
            process(i + 1, N, rest);
            list.add(i);
            process(i + 1, N, rest - 1);
            list.remove(list.size()-1);
        }
    }


    // for test
    public static void main(String[] args) {
        int n = 4;
        int k = 2;
        List<List<Integer>> ans = new C77().combine(n, k);
        for (List<Integer> an : ans) {
            System.out.println(an);
        }
    }

}
